#include "priority_stack.hpp"
#include <iostream>
#include <string>
#include <vector>

/**
 * 冒泡排序
 * 在待排序的一组数中,将相邻的两个数进行比较,若前面的数比后面的数大就交换两数,否则不交换;如此下去,直至最终完成排序.
 * 时间复杂度:O(n^2)
 * 空间复杂度:O(1)
 */
template <class T> void BubbleSort(std::vector<T> &v)
{
    for (int j = v.size() - 1; j > 0; j--)
    {
        for (int i = 0; i < j; i++)
        {
            if (v[i] > v[i + 1])
            {
                std::swap(v[i], v[i + 1]);
            }
        }
    }
}
/**
 * 选择排序
 * 在待排序的一组数中,将最小的数与第一个数交换,然后从第二个数开始,将最小的数与第二个数交换,依次类推,直至完成排序.
 * 时间复杂度:O(n^2)
 * 空间复杂度:O(1)
 */
template <class T> void SelectionSort(std::vector<T> &v)
{
    for (int i = 0; i < v.size() - 1; i++)
    {
        int min = i;
        for (int j = i + 1; j < v.size(); j++)
        {
            if (v[j] < v[min])
            {
                min = j;
            }
        }
        std::swap(v[i], v[min]);
    }
}
/**
 * 插入排序
 * 从第2个元素开始,将当前元素插入到前面已经排序的元素中,从而获得一个有序的序列。
 * 时间复杂度:O(n^2)
 * 空间复杂度:O(1)
 */
template <class T> void InsertionSort(std::vector<T> &v)
{
    for (int i = 1; i < v.size(); i++)
    {
        int j = i;
        while (j > 0 && v[j] < v[j - 1])
        {
            std::swap(v[j], v[j - 1]);
            j--;
        }
    }
}

/**
 * 堆排序
 */
template <class T> void HeapSort(std::vector<T> &v)
{
    PriorityStack<T> pq;
    for (T ve : v)
    {
        pq.push(ve);
    }
    v = pq.TopK(v.size());
}
/**
 * 希尔排序
 *
 */
bool CheckSort(std::vector<int> &v)
{
    for (int i = 0; i < v.size() - 1; i++)
    {
        if (v[i] > v[i + 1])
        {
            return false;
        }
    }
    return true;
}

template <class T> void TestSort(std::vector<T> &v, void (*fun)(std::vector<T> &v), std::string tag)
{
    std::vector<T> vop(v);
    BubbleSort(vop);
    std::cout << tag << " result: " << std::boolalpha << CheckSort(vop) << std::endl;
}

int main()
{
    std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 2, 4, 5, 6};

    TestSort(v, BubbleSort, "BubbleSort");
    TestSort(v, SelectionSort, "SelectionSort");
    TestSort(v, InsertionSort, "InsertionSort");
    TestSort(v, HeapSort, "HeapSort");
    return 0;
}